UVa/10005 - Packing polygons/10005.2.cpp

   1 /*
   2   Accepted. Graham Scan.
   3  */
   4 #include <iostream>
   5 #include <vector>
   6 #include <algorithm>
   7 #include <iterator>
   8 #include <math.h>
   9 #include <stdio.h>
  10
  11 using namespace std;
  12
  13
  14 //const double pi = 2*acos(0);
  15 const double pi = 3.14159265;
  16
  17 struct point{
  18   int x,y;
  19   point() {}
  20   point(int X, int Y) : x(X), y(Y) {}
  21 };
  22
  23 point pivot;
  24
  25 ostream& operator<< (ostream& out, const point& c)
  26 {
  27   out << "(" << c.x << "," << c.y << ")";
  28   return out;
  29 }
  30
  31 inline double dist(const point &a, const point &b){
  32   return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
  33 }
  34
  35 inline int distsqr(const point &a, const point &b){
  36   return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
  37 }
  38
  39 //retorna si c esta a la izquierda de el segmento AB
  40 inline int cross(const point &a, const point &b, const point &c){
  41   return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
  42 }
  43
  44 //Self < that si esta a la derecha del segmento Pivot-That
  45 bool angleCmp(const point &self, const point &that){
  46   int t = cross(pivot, that, self);
  47   if (t < 0) return true;
  48   if (t == 0){
  49     //Self < that si está más cerquita
  50     return (distsqr(pivot, self) < distsqr(pivot, that));
  51   }
  52   return false;
  53 }
  54
  55
  56 //vector p tiene los puntos ordenados anticlockwise
  57 vector<point> graham(vector<point> p){
  58   //Metemos el más abajo más a la izquierda en la posición 0
  59   for (int i=1; i<p.size(); ++i){
  60     if (p[i].y < p[0].y || (p[i].y == p[0].y && p[i].x < p[0].x ))
  61       swap(p[0], p[i]);
  62   }
  63
  64   pivot = p[0];
  65   sort(p.begin(), p.end(), angleCmp);
  66
  67   //Ordenar por ángulo y eliminar repetidos.
  68   //Si varios puntos tienen el mismo angulo el más lejano queda después en la lista
  69   vector<point> chull(p.begin(), p.begin()+3);
  70
  71   //Ahora sí!!!
  72   for (int i=3; i<p.size(); ++i){
  73     while ( chull.size() >= 2 && cross(chull[chull.size()-2], chull[chull.size()-1], p[i]) <= 0){
  74       chull.erase(chull.end() - 1);
  75     }
  76     chull.push_back(p[i]);
  77   }
  78
  79   return chull;
  80 }
  81
  82 int main(){
  83   int cases;
  84   cin >> cases;
  85   bool first = true;
  86   while (cases--){
  87     if (!first) cout << endl;
  88     first = false;
  89     int n, l;
  90     cin >> n >> l;
  91     vector<point> p;
  92     for (int i=0; i<n; ++i){
  93       int x, y;
  94       cin >> x >> y;
  95       p.push_back(point(x,y));
  96     }
  97
  98     vector<point> chull = graham(p);
  99
 100     /*cout << "chull es:  " << endl;
 101       for (int i=0; i<chull.size(); ++i){
 102       cout << chull[i] << " ";
 103       }
 104       cout <<  endl;*/
 105
 106     double perimeter = 0.0;
 107     for (int i=0; i<chull.size(); ++i){
 108       int j = (i+1)%chull.size();
 109       perimeter += dist(chull[i], chull[j]);
 110     }
 111
 112     printf("%.0f\n", perimeter + 2*pi*l);
 113   }
 114   return 0;
 115 }